#include <set>
#include <vector>

const int cInfinity = 1000 * 1000 * 1000;
pair <vector <int>, vector <int> > dijkstra(vector <vector <pair <int, int> > > &g, int start)
// (g) here is the incidental list, where edge is a pair of distance-vertex
{
	vector <int> dist(g.size(), cInfinity);
	vector <int> prev(g.size());
	dist[start] = 0;
	
	set <pair <int, int> > que; // set of pair of distance-vertex
	// you may use any alternate structure for fast minimum exjecting, such as heap
	que.insert(make_pair(dist[start], start);
	while (!que.empty())
	{
		// exjecting minimum
		int current = que.begin()->second;
		que.erase(que.begin());
		
		// for each vertex incidental to (current), optimizing dist[]
		for (int loop = 0; loop < g[current].size(); loop++)
		{
			int to_inx = g[current][loop].second,
				to_dist = g[current][loop].first;
			// ? previous selected path is longer then path through (current)
			if (dist[to_inx] > dist[current] + to_dist)
			{
				// optimising this edge
				que.erase(make_pair(dist[to_inx], to_inx));
				dist[to_inx] = dist[current] + to_dist;
				que.insert(make_pair(dist[to_inx], to_inx));
				// saving previous vertex on shortest path
				prev[to_inx] = current;
			}
		}
	}
	
	return make_pair(dist, prev);
}